之前介绍过单模式串匹配的高效算法:BM和KMP 以及 基于多模式串的匹配数据结构Trie树。

1. BM和KMP 单模式串匹配算法细节

2. Trie树 多模式串的高效匹配数据结构

当有这样的需求：对于输入的主串，需要替换其中的敏感词为其他字符，也就是需要对trie树中的字符串逐个匹配，来判断该字符串是否在主串中，从而将其替换为制定字符。比如输出主串：abacdab , 使用Trie树构建的字符集如下：abc, ac,dab，最终替换的主串为: aba***** 。

如果用Trie树的匹配方式：

会拿着每一个trie树中的字符串 来和主串匹配，如果主串中没有这个字符串，则匹配trie树中的下一个字符串。

以root的26个字符为外层循环进行遍历，如果root->children_[des[i]-‘a’]不为空，则循环当前的trie树中的字符，且主串的i++，直到Trie树的叶子结点，发现当前trie树的这个字符串没法匹配，则从trie树的root重新开始匹配下一个trie树中的字符串。

基本的代码如下：

其中的AcNode也就是Trie-tree 中的TrieNode，下文的代码其实已经完成了Trie树的构建，相关的代码可以在开头的Trie树实现中查看。

主要增加了一个失败指针，构建Ac自动机的过程 主要是将多个模式串构建成一个Trie树，并在其上构建失败指针（类似KMP的失效函数next数组）。

还是之前描述过的，AC自动机是为了减少模式串的匹配次数，每次Trie树中的模式串失配之后不需要从Trie的root节点重新开始匹配，而是跳转到下一个可能匹配的模式串的指定位置继续匹配，这个位置就是由失败指针来控制的。

举个例子:

一下Trie树为模式串构建的，包含字符串abcd, bcf, c

有一个从 从abcd字符串中C 指向bcf中的c 的指针，当我们在abcd中 d处匹配失效的时候可以继续从bcf 开始匹配，因为之前的bc已经在主串中存在了，所以不需要再从b开始进行匹配了。

前面的例子 能够对失败指针在Trie树中的匹配作用有一个整体的了解，会减少Trie树中的匹配次数。

注意，Ac自动机的场景是在一个主串中匹配多个模式串，一般用于敏感词过滤，匹配的过程就是减少在模式串中构成的Trie树的匹配次数。

在KMP算法构建失效函数的过程中提到了一个最长可匹配前缀子串，因为KMP是从左向右匹配，所以在遇到坏字符的时候每次模式串的滑动需要滑动大最长可匹配前缀子串的位置。这里也是类似的，可以看到如上例子: 模式串匹配到abcd的d字符时 发现和主串的f不匹配，这个时候c为失效指针起作用的位置，即在abc是已经和主串达成匹配的字符串了，只需要找到abc中的最长可匹配后缀子串即可。

后缀子串 就是最后一个字符串相同的子串，比如 abc 的后缀子串是 c, bc；最长可匹配后缀子串就是 Trie树中的其他字符串能够和bc匹配的前缀子串，比如案例中的bcf字符串 ，其前缀子串为b,bc ，则bc最长且和abc的后缀子串匹配。所以只需要让每一个失败指针保证指向的是最长可匹配后缀子串的结束位置即可。

可以像kmp算法那样，当我们要求某个节点的失败指针的时候，可以通过已经求得的、深度更小的节点的失败指针来推导，从而能够逐层求解每个节点的失败指针，也就是失败指针的构建会层次遍历Trie树。

构建失效指针的过程如下：

变更案例Trie树如下

其中root节点的失败指针为null，假设我们知道了字符c对应的TrieNode p的失败指针为 q，那我们想要求p的子节点pc的失败指针。如果pc->data == qc->data，即p的子节点字符和q的子节点字符相同，则将节点pc的失败指针指向qc, pc->fail = qc

如果节点q没有子节点 或 q的子节点字符和pc的字符不想等，则让q = q->fail，再看看q的子字符是否和pc的字符相等，依次直到q==root,也就是找不到子节点和pc匹配的节点，就让pc->fail=root就好了。

构建的过程需要层次遍历Trie树，依赖当前节点的上一个节点构建失败指针，将处于当前层的所有失败指针都构建完成。

有了失败指针的完整位置，也就知道了能够快速匹配的捷径。

如下已经完成了所有节点失败指针构建的 Trie树

主串为 abcdhe

匹配过程中 输入的主串从 i=0开始，AC自动机从指针 p=root开始，假设主串是b

abcdhe 为主串的匹配过程可以带入以上两个case, 非常容易理解。

以下逻辑为匹配模式串并输出 模式串在主串中的起始位置，并且完成模式串在主串中的替换：